class HashTable {
    constructor () {
        this.storage = []
        this.count = 0
        this.limit = 7
    }

    // 设计哈希函数
    // 1）将字符串转成比较大的数字：hashCode
    // 2）将大的数字hashCode压缩到数组范围（大小）之内
    hashFunc (str, size) {
        // 1、定义hashCode变量
        let hashCode = 0

        // 2、霍纳算法，来计算hashCode的值
        for (let i = 0, len = str.length; i < len; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i)
        }

        // 3、取余操作
        let index = hashCode % size
        return index
    }

    // 1、根据key获取索引值
    // 目的：将数据插入到对应的位置
    // 2、根据索引值去除bucket
    //  1）如果同不存在，创建桶，并且防止在该索引的位置
    // 3、判断新增还是修改原来的值
    //  1）如果已经有值了，那就修改
    //  2）没有就添加
    put (key, value) {
        // 1、根据key获取对应的index
        let index = this.hashFunc(key, this.limit)

        // 2、根据index获取bucket
        let bucket = this.storage[index]

        // 3、判断bucket是否为null
        if (!bucket) {
            bucket = []
            this.storage[index] = bucket
        }

        // 4、判断是否修改数据
        for (let i = 0, len = bucket.length; i < len; i++) {
            let tuple = bucket[i]
            if (tuple[0] == key) {
                tuple[1] = value
                return
            }
        }

        // 5、添加操作
        bucket.push([key, value])
        this.count += 1

        // 判断是否需要扩容
        if (this.count > this.limit * 0.75) {
            this.resize(this.limit * 2)
        }
    }

    // 获取操作
    get (key) {
        // 1、根据key获取对应的index
        let index = this.hashFunc(key)

        // 2、根据index获取对应的bucket
        let bucket = this.storage[index]

        // 3、判断bucket
        if (bucket == null) {
            return null
        }

        for (let i = 0, len = bucket.length; i < len; i++) {
            let tuple = bucket[i]
            if (tuple[0] == key) {
                return tuple[1]
            }
        }

        return null
    }

    remove (key) {
        // 1、根据key获取对应的index
        let index = this.hashFunc(key)

        // 2、根据index获取对应的bucket
        let bucket = this.storage[index]

        // 3、判断bucket
        if (bucket == null) {
            return null
        }

        for (let i = 0, len = bucket.length; i < len; i++) {
            let tuple = bucket[i]
            if (tuple[0] == key) {
                bucket.splice(i, 1)
                this.count -= 1
                return tuple[1]

                // 缩小容量
                if (this.limit > 7 && this.count < this.limit * 0.25) {
                    this.resize(Math.floor(this.limit / 2))
                }
            }
        }

        return null
    }

    isEmpty () {
        return this.count == 0
    }

    size () {
        return this.count
    }

    // 哈希表扩容/缩容
    resize (newLimit) {
        // 1、保存就得数组内容
        let oldStorage = this.storage

        // 2、重置所有的属性
        this.storage = []
        this.count = []

        // 处理扩容的大小，如果不是质数，将获取其相邻最近且大于其的质数
        const newPrime = this._getPrime(newLimit)
        this.limit = newPrime

        // 3、bucket中有数据，那么取出数据，重新插入
        for (var i = 0, len = oldStorage.length; i < len; i++) {
            let bucket = oldStorage[i]
            if (bucket == null) {
                continue
            }

            for (let j = 0, len = bucket.length; j < len; j++) {
                let tuple = bucket[i]
                this.put(tuple[0], tuple[1])
            }
        }
    }

    // 获取与num相邻最近质数
    _getPrime (num) {
        while (!this._isPrime(num)) {
            num++
        }
        return num
    }

    // 判断一个数是否质数
    _isPrime (num) {
        let temp = Number.parseInt(Math.sqrt(num))
        for (let i = 2; i < temp; i++) {
            if (num % i == 0) {
                return false
            }
        }
        return true
    }
}

export default HashTable
